#ifndef CONJUNTO_HPP_
#define CONJUNTO_HPP_

#include <iostream>
#include "Conj.h"

using namespace std;
using namespace aed2;

class Trie
{

	public:

		// Constructor. Genera un trie vacío.
		Trie();
		// Destructor. Debe dejar limpia la memoria.
		~Trie();
		// Agrega tema a un conjunto de autores
		void agregarTema(const char*,  const Conj<string>&);
		// Agrega el autor al Trie
		void agregarAutor(const char*);

		const Conj<string>& FTS(const char*, Conj<string> &) const;

		bool estaDefinido(const char*) const;
		//{Se corresponde a la función obtener del TAD, es decir obtiene el significado de una clave.} 
		//{Precondición: está definido en el trie}
		Conj<string>& obtenerClave(const char*) const;  //{estaDefinido?(t,s)}

	private:

		// la representación de un nodo interno.
		struct Nodo
		{
			bool esClave;
			Conj<string> *conjunto;
			// el elemento representa el nodo es de 256 elementos.
			Nodo *array[256];
			// el constructor que representa el nodo.
			
			Nodo() {

				conjunto = NULL;
				esClave = false;

				for(int i = 0; i < 256; i++)
					array[i] = NULL;
			
			}

		};

		// Agrega una clave en el trie
		void definirClave(const char*, bool);

		void devolverTodo(Nodo*, Conj<string>&) const;

		void DestructorAuxiliar(Nodo*);

		//puntero a la raíz del trie.
		Nodo* raiz;
		
};



Trie::Trie():raiz(NULL){}

Trie::~Trie() {

	DestructorAuxiliar(raiz);

}

void Trie::DestructorAuxiliar(Nodo* p){

    if(p != NULL){
        for(int i = 0; i < 255; i++){
            DestructorAuxiliar(p->array[i]);
        }
        if(p->esClave){
            delete p->conjunto;
        }
        delete p;

    }
}

void Trie::definirClave(const char *p, bool b){

		const char *aux = p;
		Nodo **n = &raiz;

		while(*p){

			if(*n == NULL)
				*n = new Nodo();

			n = &(((*n) -> array)[(int)(*p)]);

			if(*n == NULL)
				*n = new Nodo();

			p++;
		}

		Conj<string>* c = new Conj<string>;

		(*n) -> esClave = true;

		if(b){


			(*n) -> conjunto = c;   //debería apuntar a un conjunto vacío
		}
		else
		{
			(*n) -> conjunto = c;  //debería apuntar a un conjunto que autocontenga el tema
			(*c).AgregarRapido(aux);
			
		}

}

Conj<string>& Trie::obtenerClave(const char* p) const{

	Nodo *aux = raiz;
	while(*p){

		aux = (aux -> array)[(int)(*p)];
		p++;
	}

	return *(aux -> conjunto);
}

void Trie::agregarTema(const char* s, const Conj<string>& c) { //{la referencia es a un conjuto de autores que pertencen al trie}

	Conj<string>::const_Iterador it = c.CrearIt();

	while(it.HaySiguiente()){

		(obtenerClave(&(it.Siguiente())[0])).AgregarRapido(s);
		it.Avanzar();

	}


	definirClave(s,false); //¡define el tema en el trie!

}


void Trie::agregarAutor(const char* s){
	definirClave(s,true);
}


template<typename T>
void Union(Conj<T>& c1, const Conj<T>& c2){

    typename Conj<T>::const_Iterador it = c2.CrearIt();

    while(it.HaySiguiente()){

        c1.Agregar(it.Siguiente());
        it.Avanzar();

    }

}


const Conj<string>& Trie::FTS(const char* p, Conj<string> &res) const{

	Nodo* const *n = &raiz;

	while(*p && *p != '*' && *n != NULL){

		n = &(((*n) -> array)[(int)(*p)]);
		p++;
	}

	if(*n != NULL && (*n) -> conjunto != NULL && (*n) -> esClave && *p != '*')

		return *((*n) -> conjunto);

	if(*p == '*')
		devolverTodo(*n, res);

	return res;

}

void Trie::devolverTodo(Nodo* p, Conj<string> &c) const{

	if (p != NULL)
	{
	
		if(p -> esClave)
			Union(c, *(p->conjunto));

		for(int i = 0; i < 256; i++)
			devolverTodo((p->array)[i],c);

	}

		
}


bool Trie::estaDefinido(const char* p) const {

	Nodo *const *n = &raiz;

	while(*n != NULL && *p){

		n = &(((*n) -> array)[(int)(*p)]);
		p++;

	}

	return (*n != NULL) && ((*n) -> conjunto) != NULL && ((*n) -> esClave);
}




#endif // CONJUNTO_HPP_
